Insert Delete GetRandom O(1)
Leetcode #380 | Medium | Хэш-таблицы | Математика | Design
Идея
HashMap + ArrayList в листе храним значения, в мапе значение: индекс_в_листе, для удаления свопаем элемент в листе с последним и удаляем за O(1), попутно обновляем мапу
Random random = new Random(); int rand = random.nextInt(size); <- для рандома
Big-O
- Время
O(1) - Память
O(N)
Код
class RandomizedSet {
private List<Integer> list = new ArrayList<>();
private Map<Integer, Integer> map = new HashMap<>();
private Random rand = new Random();
public boolean insert(int val) {
if (map.containsKey(val)) return false;
list.add(val);
map.put(val, list.size() - 1);
return true;
}
public boolean remove(int val) {
if (!map.containsKey(val)) return false;
int index = map.get(val);
int lastVal = list.get(list.size() - 1);
list.set(index, lastVal);
map.put(lastVal, index);
list.remove(list.size() - 1);
map.remove(val);
return true;
}
public int getRandom() {
return list.get(rand.nextInt(list.size()));
}
}